package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/reorder-list/">重排链表</a>
 * <p>给定一个单链表 L 的头节点 head ，单链表 L 表示为：</p>
 * <pre>L0 → L1 → … → Ln - 1 → Ln</pre>
 * <p>请将其重新排列后变为：</p>
 * <pre>L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …</pre>
 * <br><b>不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,2,3,4]
 *      输出：[1,4,2,3]
 *
 * 示例 2：
 *      输入：head = [1,2,3,4,5]
 *      输出：[1,5,2,4,3]
 * </pre>
 * <b>提示：</b>
 * <li>链表的长度范围为 [1, 5 * 10^4]</li>
 * <li>1 <= node.val <= 1000</li>
 *
 * @author c2b
 * @since 2023/5/4 14:02
 */
public class LC0143ReorderList_M {

    public void reorderList1(ListNode head) {
        if (head == null) {
            return;
        }
        // 快慢指针找到链表中点
        ListNode mid = middleNode(head);
        ListNode list1 = head;
        ListNode list2 = mid.next;
        // 将list2断开：list1 为第一段链表，list2 为第二段链表
        mid.next = null;
        // 反转list2
        list2 = reverseList(list2);
        // 合并两个链表
        while (list1 != null && list2 != null) {
            // 记录下一个节点
            ListNode list1TempNode = list1.next;
            ListNode list2TempNode = list2.next;
            list1.next = list2;
            list1 = list1TempNode;
            list2.next = list1;
            list2 = list2TempNode;
        }
    }

    /**
     * 反转链表
     */
    private ListNode reverseList(ListNode list2) {
        ListNode prev = null;
        ListNode curr = list2;
        ListNode next;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }


    /**
     * 利用快慢指针找到链表的中点。
     * <p>如果链表中元素的个数为奇数个，返回正中间那个。如果链表中元素的个数为偶数个，找出第一段链表的最后一个</p>
     * <p>例如：</p>
     * <pre>
     *     1->2->3->4->5 返回3
     *     1->2->3->4    返回2
     * </pre>
     */
    private ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


    public void reorderList2(ListNode head) {
        if (head == null) {
            return;
        }
        List<ListNode> list = new ArrayList<>();
        ListNode curr = head;
        while (curr != null) {
            list.add(curr);
            curr = curr.next;
        }
        int leftIndex = 0;
        int rightIndex = list.size() - 1;
        while (leftIndex <= rightIndex) {
            if (leftIndex == rightIndex) {
                break;
            } else {
                list.get(leftIndex).next = list.get(rightIndex);
                ++leftIndex;
                list.get(rightIndex).next = list.get(leftIndex);
                --rightIndex;
            }
        }
        list.get(leftIndex).next = null;
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        LC0143ReorderList_M lc0143ReorderList_m = new LC0143ReorderList_M();
        lc0143ReorderList_m.reorderList1(node);

        while (node != null) {
            System.out.println(node.val);
            node = node.next;
        }
    }
}
